A novel local search based on variable-focusing for random K-SAT

摘要

We introduce a new local search algorithm for satisfiability problems. Usualapproaches focus uniformly on unsatisfied clauses. The new method works bypicking uniformly random variables in unsatisfied clauses. A Variable-basedFocused Metropolis Search (V-FMS) is then applied to random 3-SAT. We show thatit is quite comparable in performance to the clause-based FMS. Consequences foralgorithmic design are discussed.